package vip.zhenzicheng.algorithm.leetcode.sort;

import java.util.PriorityQueue;

/**
 * <a href="https://leetcode.cn/problems/kth-largest-element-in-an-array/">数组中的第K个最大元素 [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-06-20 13:09
 */
public class KthLargestElementInAnArray_215 {

  // 作弊法，使用原生JDK快速排序
  // public int findKthLargest(int[] nums, int k) {
  //     Arrays.sort(nums);
  //     int N = nums.length;
  //     return nums[N - k];
  // }

  // 快排
  // public int findKthLargest(int[] nums, int k) {
  //   int target = nums.length - k; // 第k大的元素下标
  //   int L = 0, R = nums.length - 1;
  //   while (true) {
  //     int index = FastSort.partition(nums, L, R);
  //     if (index == target) {
  //       return nums[target];
  //     } else if (index < target) {
  //       L = index + 1;
  //     } else {
  //       R = index - 1;
  //     }
  //   }
  // }

  // JDK原生优先队列实现（堆排序），默认最小堆，最大堆需要实现Comparator
  // 使用堆的好处就是可以不用全部load到内存，规定有限堆然后不断替换堆顶元素
  public int findKthLargestWithPQ(int[] arr, int k) {
    // 使用一个含有k个元素的最小堆
    PriorityQueue<Integer> pq = new PriorityQueue<>(k);

    for (int i = 0; i < k; i++) { // 最小堆定义，第一个元素是最小，所以只需要放一个长度k的最小堆，等所有元素都遍历以后最底下一定是最大元素，最小的就是倒数第k小的元素
      pq.add(arr[i]);
    }

    for (int i = k; i < arr.length; i++) {
      if (arr[i] > pq.peek()) { // 替换堆顶元素
        pq.poll();
        pq.offer(arr[i]);
      }
    }
    return pq.poll();
  }
}
